第9.8节 SMO算法
各位朋友大家好，欢迎来到月来客栈，我是掌柜空字符。
本期推送内容目录如下，如果本期内容对你有所帮助，欢迎点赞、转发支持掌柜！
9.8 SMO算法 9.8.1 坐标上升算法 9.8.2 SMO算法思想 9.8.3 SMO算法原理 9.8.4 偏置求解 9.8.5 SVM算法求解示例 9.8.6 小结 引用
9.8 SMO算法
在第9.7节中，笔者分别就SVM中软间隔与硬间隔目标函数的求解过程进行了介绍，但是在实际应用过程中，从效率的角度来讲那样的做法显然是不可取的，尤其是在大规模数据样本和稀疏数据中[1]。在接下来的这节内容中，笔者将介绍一种新的求解算法，即序列最小化优化算法来解决这一问题。
序列最小优化算法（Sequential Minimal Optimization,SMO）于1998年由John Platt所提出，并且SMO算法初次提出的目的就是为了解决SVM的优化问题[2]。SMO算法是一种启发式的算法，它在求解过程中通过以分析的方式来定位最优解可能存在的位置，从而避免了传统方法在求解中所遭遇的大量数值计算问题，并且最终以迭代的方式来求得最优解。在正式介绍SMO算法之前，笔者将先介绍SMO算法的基本原理——坐标上升算法（Coordinate Ascent）。
9.8.1 坐标上升算法
在第2.5节内容中，笔者详细地介绍了什么是梯度下降算法及梯度下降算法的作用。对于一个待优化的目标函数来讲，在初始化一个起始位置后，便可以以该点为基础每次沿着该点梯度的反方向向前移动一小步，以此来迭代求解，以便得到目标函数的全局（局部）最优解，而所谓的坐标上升（下降）算法可以看作初始位置只沿着其中的一个（或几个）方向移动来求解得到目标函数的全局（局部）最优解[3]，如图9-14所示。
在图9-14中，虚线为目标函数的等高线，黑色箭头曲线为梯度上升算法最大化目标函数的求解过程，而黑色箭头折线为坐标上升算法最大化目标函数的求解过程。
具体地，对于待求解目标函数来讲可以通过如下步骤进行求解。
(1) 随机将向量初始化为初始参数值。
(2) 在中依次将选择为变量并将其他参数固定为常量，然后求目标函数关于的导数并令其为0求得。
(3) 重复执行步骤(2)直到目标函数收敛或者误差小于某一阈值结束。
例如在上面这个示例中和的求解表达式分别为
那么在初始化一组和后，便可以通过式(9.131)来迭代以便求解得到和的解。
同时，上述步骤(2)对于顺序的选择这里采用了最为简单的按顺序依次进行，一种更优的做法便是每次选择余下常量中能够使目标函数产生最大增量的参数作为优化对象。
9.8.2 SMO算法思想
根据9.7.3节中式(9.118)可知，SVM软间隔最终需要求解的目标函数为
假设随机初始化后的均满足式(9.132)中的约束条件，现在通过坐标上升算法来求解。如果此时将固定为常量，将 固定为变量来求解 ，则能求解得到吗？答案是不能[4]。因为根据式(9.132)中第2个约束条件有
进一步，在式(9.133)两边同时乘上有
根据式(9.134)可知，完全取决于，如果固定，也就意味着也是固定的，因此，在这样的情况下每次至少需要同时选择两个参数为变量，同时再固定其他参数为常量，才能够最终求得所有参数。
此时，假设固定不变来求解参数和。根据式(9.132)中的约束条件有
由于此时式(9.135)右边是固定的，因此可以用一个常数来表示
进一步，可以将表示为
此时，式(9.132)中的目标函数便可以改写为
在式(9.138)中，由于此时将固定为常数，因此其可以简单地表示为一个关于的一元二次 多项式（这一点也可以从式(9.96)中看出）。
接着，对于多项式(9.139)来讲通过令的导数为0便可以轻易求得的取值，然后将代入式(9.136)即可得到的值。进一步，按照相同的过程便可求得的值，最后重复执行上述整个过程便可以迭代求解得到的值。
以上就是SMO算法求解的主要思想。虽然看起来不太复杂，但是里面仍旧有很多值得深究的内容，下面开始正式介绍SMO算法的原理。
9.8.3 SMO算法原理
为了更加广义地表示SVM软间隔中的优化问题，可以通过如下形式来表示待求解的优化问题
其中为任意核函数。
进一步，不失一般性，这里假设首先将参数和选择为变量，将其他参数固定为常量。于是式(9.140)便可以改写成如下形式[1]
其中，表示与和无关的常量。
同时，记
则目标函数(9.141)可以改写为
将代入式(9.143)便可以得到一个只含有变量的目标函数
进一步，式(9.144)关于的导数为
令式(9.145)为0，可以得到
此时，记
那么在初始化一组和后，将式(9.147)和代入式(9.146)有
将式(9.148)进一步化简后可得
至此，便初步求得了的求解表达式。为什么是初步呢？因为此时求得的还没有经过约束条件裁剪。
为你认可的知识付费，欢迎订阅本专栏阅读更多优质内容！
由式(9.141)中的第1个约束条件可知，和的解只能位于这个正方形盒子中。进一步，由式(9.141)中的第2个约束条件可知，和还必须位于平行于盒子对角线的线段上，如图9-15所示。